Social media networks have experienced a meteoric rise in popularity. Information spread much faster in social networks than any other communication method as of this writing. This ease of information dissemination can be a double-edged sword, however, as social networks can also be used to spread rumors or computer malware. In such circumstances, detecting and determining the source of rumors or misinformation in a social network becomes valuable as a part of an affected party's damage control.
One potential source of information/misinformation may be a result of a node with a high degree of centrality (e.g., a node with a large number of friends on Facebook). This, however, is unlikely, because, in general, every node in a social network has the potential to spread information/misinformation.
It may be possible to use information from a snapshot of infected nodes to identify the source of information/misinformation. This requires the assumption that all nodes in the network monitor and report their status, which is not practical in large-scale social networks. Furthermore, this assumes that the underlying social graph is a regular tree. In general, however, an underlying social graph can be any type of graph.
It may also be possible to use a subset of nodes (called sensors) in the social network to find the source of information/misinformation. The foregoing methods require a large number of nodes in the network to act as sensors which is generally impractical. Furthermore, these methods do not consider the varying inter-node relationship strengths.